import numpy as np
file_path = 'Data.txt'
out_path = 'basic_result.txt'

# 打开并读取文件
with open(file_path, 'r') as f:
    lines = f.readlines()

degree = []
max_node_id = 0
max_to_id = 0
matrix = {}
dead_ends = []

# 遍历每一行
for line in lines:
    # 分割行并将结果添加到列表中
    from_node_id, to_node_id = map(int, line.split())
    if(from_node_id > max_node_id): # 如果from_node_id大于max_node_id，说明有新的节点出现 
        for i in range(max_node_id, from_node_id ):
            matrix[i] = [] # 初始化新节点的邻接表
            degree.append(0)
        max_node_id = from_node_id
    
    if(to_node_id > max_to_id):
        max_to_id = to_node_id
        
    degree[from_node_id - 1] += 1
    matrix[from_node_id - 1].append(to_node_id - 1)

node_nums = max(max_node_id, max_to_id) 
dead_ends = [i for i in range(node_nums) if degree[i] == 0]

rank_old = np.ones(node_nums) / node_nums
d = 0.85
epsilon = 1e-8

while True:
    rank_new = np.ones(node_nums) * (1 - d) / node_nums
    rank_new += np.sum([rank_old[i]for i in dead_ends])* d /node_nums
    #两种处理dead_end的方式，一次性处理所有dead ends，或者每次迭代都进行判断处理

    for i in range(node_nums):
        for j in matrix[i]: 
            rank_new[j] += d * rank_old[i] / degree[i]
        
    diff = np.abs(rank_new - rank_old).sum()
    if diff < node_nums*epsilon:
        break
    
    rank_old = rank_new

top_indices = np.argsort(rank_new)[::-1][:100]
top_values = rank_new[top_indices]

for i in range(100):
    print(f"Index: {top_indices[i] + 1}, Value: {top_values[i]}")

with open(out_path, 'w') as f:
    for i in range(100):
        f.write(f"{top_indices[i] + 1} {top_values[i]}\n")




